package com.practice.niuke.new_direct_practice.class16;

/**
 * 给定一个数组arr，已知除了一种数只出现1次之外，剩下所有的数都出现了k次，如
 * 何使用O(1)的额外空间，找到这个数。
 */
public class Code04_KTimesOneTime {

    /**
     * 主函数（TODO：标记主函数）
     *
     * @param arr 原数组
     * @param k   k
     * @return int
     */
    public static int onceNum(int[] arr, int k) {
        // 准备一个长度为32的int型数组，用于存放k进制数的各个位数
        int[] eO = new int[32];
        for (int i = 0; i != arr.length; i++) {
            // 遍历arr，将arr中的元素变为k进制数，并将其填入准备的32位长度的int型数组中，
            // 已经填写了数为位置上直接加上去
            setExclusiveOr(eO, arr[i], k);
        }
        // 将长度为32的int型数组的每一个元素，模上k；
        // 将剩余的不为0的位置的数，按照k进制数转换为10进制数的方式转换
        int res = getNumFromKSysNum(eO, k);
        return res;
    }

    /**
     * 将int型数字变为k进制数，并将其填入准备的长度为32的int型数组中，已经填写了数为位置上直接加上去
     *
     * @param eO    准备的长度为32的int型数组
     * @param value nt型数字
     * @param k     k
     */
    public static void setExclusiveOr(int[] eO, int value, int k) {
        int[] curKSysNum = getKSysNumFromNum(value, k);
        for (int i = 0; i != eO.length; i++) {
            eO[i] = (eO[i] + curKSysNum[i]) % k;
        }
    }

    public static int[] getKSysNumFromNum(int value, int k) {
        int[] res = new int[32];
        int index = 0;
        while (value != 0) {
            res[index++] = value % k;
            value = value / k;
        }
        return res;
    }

    /**
     * 将长度为32的int型数组的每一个元素，模上k；
     * 将剩余的不为0的位置的数，按照k进制数转换为10进制数的方式转换
     *
     * @param eO 长度为32的int型数组
     * @param k k
     * @return int
     */
    public static int getNumFromKSysNum(int[] eO, int k) {
        int res = 0;
        for (int i = eO.length - 1; i != -1; i--) {
            res = res * k + eO[i];
        }
        return res;
    }

    public static void main(String[] args) {
        int[] test1 = {1, 1, 1, 2, 6, 6, 2, 2, 10, 10, 10, 12, 12, 12, 6, 9};
        System.out.println(onceNum(test1, 3));

        int[] test2 = {-1, -1, -1, -1, -1, 2, 2, 2, 4, 2, 2};
        System.out.println(onceNum(test2, 5));

    }

}